package vip.zhenzicheng.algorithm.leetcode.stack_queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * <a href="https://leetcode.cn/problems/valid-parentheses/">有效的括号 [简单]</a>
 * <pre>
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 1. 左括号必须用相同类型的右括号闭合。
 * 2. 左括号必须以正确的顺序闭合。
 * <br/>
 * 示例 1：
 *    输入：s = "()"
 *    输出：true
 * 示例 2：
 *    输入：s = "()[]{}"
 *    输出：true
 * 示例 3：
 *    输入：s = "(]"
 *    输出：false
 * 示例 4：
 *    输入：s = "([)]"
 *    输出：false
 * 示例 5：
 *    输入：s = "{[]}"
 *    输出：true
 * 提示：
 *    1 <= s.length <= 104
 *    s 仅由括号 '()[]{}' 组成
 * </pre>
 *
 * @author zhenzicheng
 * @date 2022-06-11 11:29
 */
public class ValidParentheses_20 {

  public static void main(String[] args) {
    ValidParentheses_20 test = new ValidParentheses_20();
    String s = "(]";
    System.out.println(test.isValid(s));
  }

  public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>(); // 模拟栈
    int len = s.length();
    int i = 0;

    while (i < len) {
      char c = s.charAt(i);
      if (c == '(') {
        stack.push(')');
      } else if (c == '[') {
        stack.push(']');
      } else if (c == '{') {
        stack.push('}');
      } else if (stack.isEmpty() || c != stack.pop()) { // 如果当前是右括号，就匹配左括号
        return false;
      }
      i++;
    }
    return stack.isEmpty();
  }
}




